package fireway;

/**
 * 快速排序算法
 * 2018年 07月 29日 星期日
 *
 * @author fireway
 */
public class QuickSort {
    private long mLArray[];

    private int mSize;

    public QuickSort(int initialCapacity) {
        mLArray = new long[initialCapacity];
        mSize = 0;
    }

    public void insert(long e) {
        mLArray[mSize++] = e;
    }

    public void display() {
        System.out.print("[");
        for (int i = 0; i < mSize; i++) {
            System.out.print(mLArray[i]);
            if (i != mSize - 1) {
                System.out.print(", ");
            }
        }
        System.out.print("]\n");
    }

    private int partitioning(int left, int right, long pivot) {
        int leftPointer = left - 1;
        int rightPointer = right;

        while(true) {
            // 相对于之前划分的代码，可以删除第一个内部while循环中对是否超越
            // 数组右端的检查，即leftPointer < right。
            // 为什么可以去除这个检测呢？这是因为选择最右端的数据项作为枢纽。
            // 所以leftPointer总会停在枢纽这个位置上。
            while(mLArray[++leftPointer] < pivot) {}

            // 但是第二个while循环中的rightPointer仍然需要这个检测。后面会讲
            // 到如何同样地消除这个检测。
            while(rightPointer > 0 && mLArray[--rightPointer] > pivot) {}

            if (leftPointer >= rightPointer) {
                break;
            } else {
                swap(leftPointer, rightPointer);
            }
        }
        swap(leftPointer, right);

        return leftPointer;
    }

    private void swap(int left, int right) {
        long temp = mLArray[left];
        mLArray[left] = mLArray[right];
        mLArray[right] = temp;
    }

    public void quickSort() {
        recQuickSort(0, mSize - 1);
    }

    private void recQuickSort(int left, int right) {
        if (right-left <= 0) {
            // if size <= 1, already sorted
            return;
        } else {
            // size is 2 or larger
            long pivot = mLArray[right];
            int partitionIndex = partitioning(left, right, pivot);
            recQuickSort(left, partitionIndex - 1);
            recQuickSort(partitionIndex + 1, right);
        }
    }
}
